#include "LinkedListWithHead.h"
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
/*
	Create_Empty_LinkedListWithHead:创建一条空链表
	
	返回值：
		返回头节点的地址
*/

struct Head*Create_Empty_LinkedListWithHead()
{
    struct Head*h = malloc(sizeof(*h));
    if(h == NULL)
        return NULL;
    h->num = 0;
    h->first = h->last = NULL;

    return h;
}
/*
	Create_input_LinkedListWithHead:用键盘上输入数据创建一条带头节点整型单链表
	
	返回值：
		返回头节点的地址
*/
struct Head*Create_input_LinkedListWithHead()
{
    struct Head*h = Create_Empty_LinkedListWithHead();
    if(h == NULL)
        return h;
    while(1)
    {
        int d;
        scanf("%d", &d);
        if(d == 0)
            break;

        //创建新的数据节点并赋值
        struct Node* pnew = malloc(sizeof(*pnew));
        if(pnew == NULL)
        {
            return h;
        }
        pnew->data = d;
        pnew->next = NULL;

        //增加链表上
        if(h->first == NULL && h->last == NULL && h->num == 0)
        {
            h->first = h->last = pnew;
        }
        else
        {
            h->last->next = pnew;
            h->last = pnew;
        }

        h->num++;
    }

    return h;
}
/*
	Print_LinkedListWithHead:输出一条带头结点的单向链表
	@h:头节点指针
	
	返回值：
		无
*/
void Print_LinkedListWithHead(struct Head*h)
{
    if(h == NULL)
    {
        return ;
    }
    printf("=========================\n");
    if(h->first == NULL && h->last == NULL && h->num == 0)//空链表
    {
        printf("num:%d\n", h->num);
    }
    else
    {
        printf("first->data:%d last->data:%d num:%d\n", h->first->data,h->last->data,h->num);
    }

    struct Node*p = h->first;
    while(p)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
   
}
/*
	Insert_node_y:在h指向的链表中，查找值为x的元素，在其前面增加一个值为y的元素
			若有多个值为x的元素则增加在第一个前面
			若没有则增加在最后
	@head:头节点指针
    @x:
    @y
    
    返回值：
    	考虑看看是否需要返回值
    	可要 ： 将头节点地址返回
    	不要 ：也行，外面也可以拿到该头节点的地址
    	在该函数中变得只是头节点内部的成员
*/
void Insert_node_y(struct Head*h, ElemType x, ElemType y)
{
    //创建新节点，并赋值
    struct Node*pnew = malloc(sizeof(*pnew));
    if(pnew == NULL)
        return ;
    pnew->data = y;
    pnew->next = NULL;

    if(h->first == NULL && h->last == NULL && h->num == 0)//空链表
    {
        h->first = h->last = pnew;
        h->num++;
        return ;
    }
    struct Node*p = h->first;
    struct Node*pre = NULL;
    while(p)
    {
        if(p->data == x)
            break;
        pre = p;
        p = p->next;

    }
    if(p)
    {
        if(p == h->first)
        {
            pnew->next = h->first;
            h->first = pnew;
        }
        else
        {
            pnew->next = p;
            pre->next = pnew;
        }
    }
    else
    {
        h->last->next = pnew;
        h->last = pnew;
    }

    h->num++;
    return ;
}
/*
	Delete_node_all_x:在head指向的链表中，查找值为x的元素，将其删除
			若有多个值为x的元素则删除所有
			若没有则不删除
	@head:头节点指针
    @x:
    
    返回值：
    	无
*/
void Delete_node_all_x(struct Head*h, ElemType x)
{
    struct Node*p = h->first;//遍历指针
    struct Node*pre = NULL;
    while(p)
    {
        if(p->data == x)
        {
            //删除操作
            if(p == h->first)//删除首节点
            {
                h->first = h->first->next;
                if(h->first == NULL)//删除的是唯一一个数据节点
                    h->last = NULL;
                p->next = NULL;
                free(p);
                p = h->first;
            }
            else if(p == h->last)//删除尾节点
            {
                h->last = pre;
                h->last->next = NULL;
                free(p);
                p = NULL;
            }
            else
            {
                pre->next = p->next;
                p->next = NULL;
                free(p);
                p = pre->next;
            }
            h->num--;
        }
        else
        {
            pre = p;
            p = p->next;
        }
    }
    
}
bool Is(struct Head*A, struct Head*B)
{
	struct Node*Pa = A->first;
    struct Node*Pb = B->first;
    struct Node*Pb_next = NULL;
    if(Pb)
        Pb_next= Pb->next;//Pb的下个起点位置
    while(Pa && Pb)
    {
        if(Pa->data == Pb->data)
        {
            Pa = Pa->next;
            Pb = Pb->next;
        }
        else
        {
            Pa = A->first;
            Pb = Pb_next;
            Pb_next = Pb_next->next;
        }
    }
    if(Pa == NULL)
    {
        return true;
    }
    else
    {
        return false;
    }
}